package Exercise;

import java.util.Scanner;

public class demo16 {
    /** 0/1背包问题 (二维实现)
      *
     * //  注释部分表示一维实现
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int [] v = new int[50];
        int [] w = new int[50];
        int [][] f = new int[100][100];//int []f = new int[100];
        for (int i = 1; i <=n ; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 0; j <=m ; j++) {
                if (j < v[i]) f[i][j] = f[i - 1][j];//表示i这一组数据已经放不下了
                //f[j] = max(f[j],f[j-v[i]+w[i]);
                else f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
        System.out.println(f[n][m]);//System.out.println(f[m]);
    }
}
